通俗易懂解释伪随机暴击算法PRD的实现原理
前言
翻了网上好多篇有关解释伪随机暴击算法的文章，但都没有解释的很通俗，理解起来有一定的门槛，所以我打算自己写一篇解释这个算法的文章，力求做到让概率论零基础的玩家也能看懂。
我本人也是一名明日方舟玩家，这篇也算是对干员澄闪的天赋暴击逻辑的一个解释吧。
文章有点长，但请耐心阅读，相信你肯定能在阅读完后对这个算法知根知底。
十分感谢@一个资深的烧饼-在算法理解上给予的指导。
完整代码会放在文末。
算法简述
暴击PRD算法的诞生是为了解决“暴击间隔不均匀”的问题，在最初的目标上，它力求给予游玩PVP游戏的玩家尽可能公平的体验。
假如一个角色的暴击率是25%，那么通过暴击率=\frac{暴击次数}{总攻击次数}等式可以很轻易地推导出“暴击次数”为1，“总攻击次数”为4。也就是说在理论上，这个角色每攻击4次，就一定会产生、且只产生1次暴击。
理想情况下，暴击的分布可以是这样的
或者是这样的
但不能是这样的
这个算法的核心思想非常简单，就是通过一系列运算方式，让“理想情况下的暴击分布”出现的概率尽可能的大，让总暴击次数集中在总攻击次数的某一区间里的概率尽可能的小。换言之，就是让总暴击次数尽可能均匀的分布在总攻击次数中。
算法思想
那该如何实现这种效果呢？
该算法是做法是“动态调整每一次攻击的暴击概率”。初始的暴击概率较低，但如果当次不暴击，下一次攻击的暴击概率就会上升，直到最后暴击概率上升到100%，即当次攻击必定暴击。而在暴击触发后，概率重置回初始的较低值，进入新一轮循环。
这样一来，暴击的触发就会形成一个“不太可能暴击->有可能暴击->很可能暴击->必定暴击”的暴击周期，总暴击次数均匀地分布在总攻击次数上的概率就大大上升了，同时从宏观上来看，该算法模拟出的综合暴击率和纸面给出的理论暴击率是无比接近的。
算法解析
该暴击算法的构成非常简单：
P(N)=C*N
P(N)表示当前攻击的暴击概率，C表示概率增量，N表示当前攻击的次数。N初始为1，如果当次攻击未暴击，N+1，否则N重置为1。
假设C是0.4：
第一次攻击，N=1，P(N)=0.4*1=0.4=40%，假设当次攻击未暴击；
第二次攻击，N=2，P(N)=0.4*2=0.8=80%，假设当次攻击还是没有暴击；
第三次攻击，N=3，P(N)=0.4*3=1.2=120%>100%，当次攻击必定暴击；
第四次攻击，N=1，P(N)=0.4*1=0.4=40%，以此类推。
很显然，算法中的C就是能否让综合暴击概率贴近理论暴击概率的关键参数。但在了解C该如何计算之前，先得知晓C（概率增量）和P（理论暴击概率）之间的关系。
我们知道，随着玩家不暴击次数的增加，P(N)会不断增长，如果C就是P，那么玩家每一次攻击的暴击概率都不会低于理论暴击概率，在非100%暴击率的情况下，该算法模拟出的综合暴击概率一定会高于理论暴击概率（理论暴击概率越低，综合暴击概率与理论暴击概率的比值就会越大，相互也就越不贴近），所以如果要让综合暴击概率尽可能地贴近理论暴击概率，C必须小于或等于P。
如此一来，C一定会位于(0,P]这样一个左闭右开的区间中（包括P但不包括0），这个区间是从0起始不断递增至P的，也就是说这个区间是有序的。对于隐藏在这样一个有序区间中的C值，我们可以用有序查找速度最快的“二分查找”来将它找出来。
看到这里你可能已经明白了：暴击PRD算法的实质就是在P(N)=C*N这样一个规则下，通过一定步骤找到一个C值，使该规则模拟出的综合暴击率接近纸面给出的理论暴击率。
当然，即便是对于同一个暴击率，这个C值也不是固定的，它取决于需求要求的“接近程度”。什么意思呢？我们知道一条对于一条无限长的直线，即便你将它切成了两半，这两半它仍然是无限长的，其中的任意一半都等于另一半，也等于一开始未被切割的直线。
同理，对于(0,P]这样一个区间，它其中包含了无数的数（如果小数点后的位数是无穷尽的，那么任意两个不同整数之间包含的数也是无穷尽的），算法会无穷尽的在这无穷多的结果中刨根问底，结果就是永远也得不出一个具体的结果（由于计算机有精度限制，所以这个区间在计算机中并不是真正的包含无穷多个数，只是算法实际跑起来可能需要等比较久才能出结果）。因此我们需要确定一个“综合暴击率与理论暴击率的接近程度”，来给二分查找定一个“终点”。
概念介绍完了，直接上算法：
在该算法中，综合暴击率与理论暴击率的接近程度被限制在0.000005以内，也就是说二者的差值只要在这个范围内，就算是符合要求。
接下来是重点，C值的计算：
初看也许不太明白，但是不用担心，我会逐行将这个函数解析的明明白白。
“最大暴击范围”是什么？为什么是这样算出来的？
根据之前的暴击算法表示P(N)=C*N，随着N不断增大，P(N)迟早会上升到100%，那N需要增大几次，P(N)才能上升到100%呢？这个“几次”就是最大暴击范围，它的意思是“要打出必定暴击，最多需要几次攻击”，以C为0.22举例，最多5次攻击（math.ceil(1.0/c)，ceil表示小数向上取整），P(N)一定会上升到100%（min(1.0,i*c)，min表示取括号内较小的那一者），那这个“5次攻击”就是最大暴击范围。
for i in range(1,n_max_fail+1)，循环体控制语句，会循环“最大暴击范围”次。
d_cur_p=min(1.0,i*c)*(1-d_pre_success_p)，再解释这一句之前，需要先阐明一些概念，说明一下这个函数的编写思路。
如果你随便抛一个六面骰子，连抛三次，要求抛的点数各不同，那这件事发生的概率是多少呢？
第一次投掷：可以是任意点数，所以它的点数的可能性是6/6，因为没有限制条件。
第二次投掷：为了与第一次的点数不同，我们只有5个选择（排除了第一次出现的点数），因此概率是5/6。
第三次投掷：这次需要排除前两次投掷出现的点数，所以只剩下四个可能的点数，概率是4/6。
将三次投掷的概率相乘，得到这样一个概率的结果：
\frac{6}{6}×\frac{5}{6}×\frac{4}{6}=\frac{5}{9}
在这个例子中，三次投掷都是独立的，它们互不干扰，无论上一次抛出的是几，都不会影响这次抛出的点数，而每次投掷骰子的概率计算，都只是简单地考虑了在上一次投掷不同点数之后的剩余可能性，所以对于相互独立的事件，它们均发生的概率就是它们单个发生概率的乘积。
那如果抛这个骰子60遍，平均抛出的点数是几呢？
在各面概率均等的情况下，理论上抛出各面的次数都是一样的，即
\frac{1}{60}(\frac{1}{6}×1×60+\frac{1}{6}×2×60+...+\frac{1}{6}×6×60)
提取公因式可得
\frac{1}{6}×1+\frac{1}{6}×2+...+\frac{1}{6}×6=3.5
没错， \sum_{第一种情况}^{最后一种情况}{(概率×概率对应的取值)}=该事件的平均取值
这就是数学期望的概念，或者说这个概念可以简单这么理解。
概念介绍完了，接下来说说函数的编写思路。
对这个函数来说， “暴击出现在哪次攻击上”也是互相独立的。
假定C为0.25，最大暴击范围为4次，那么有以下四种情况：
第1次就暴击；
第1次未暴击，第2次暴击；
第1-2次未暴击，第3次暴击；
第1-3次未暴击，第4次暴击。
具体来说——
“第1次就暴击”，d_cur_p=min(1.0,1*0.25)*(1-0)=25%，并将“第1次就暴击”的概率累加到“已经考虑到的成功概率范围d_pre_success_p”里，同时计算该情况在数学期望中所占的部分“1*0.25”，将之累加到“当前C值下，打出暴击需要的平均攻击次数d_pe”中。可以看出，d_pe的算法如下所示：
d\_pe=\sum_{第1次就暴击}^{第4次才暴击}{当前攻击为首次暴击的概率×当前攻击为首次暴击需要的攻击次数}
“第1次未暴击，第2次暴击”，d_cur_p=min(1.0,2*0.25)*(1-0.25)=37.5%，可以看到d_pre_success_p从0增加到0.25了，算法考虑到了“第1次就暴击”的可能性，因此需要“*(1-0.25)”来将“第1次就暴击的可能性”排除出去，这意味着“第1次未暴击，第2次暴击”是建立在“第1次未暴击（排除掉“第1次就暴击”的概率）”基础之上的。
后面的计算同理，“第1-2次未暴击，第3次暴击”是建立在“第1次未暴击”（将“第1次就暴击的概率”累加进d_pre_success_p里，并用(1-d_pre_success_p)将这个概率排除掉）和“第2次也未暴击” （将“第1次未暴击，第2次暴击”也累加进d_pre_success_p里，并用(1-d_pre_success_p)将这两种情况加起来一起排除掉）基础之上的。
“第1-3次未暴击，第4次暴击”乃至之后可能更多的“第i-1次未暴击，第i次暴击”皆是如此，以此类推。
看到这里你可能会产生疑问：不是说每种情况之间都是互相独立的吗，怎么后一种情况的概率都是建立在之前所有情况的概率之上的呢？
回想一开始给出的投骰子例子，“前一次投掷的结果不影响这一次投掷的结果，而每次投掷骰子的概率计算，都只是简单地考虑了在上一次投掷不同点数之后的剩余可能性”，同理，“前一次能否进入循环运算概率（打出攻击）并不影响这一次能否进入循环运算概率，能进入循环运算的次数是最大暴击范围（类比骰子的面数）定的，而每次d_cur_p的计算，都只是考虑到‘前i-1次都未暴击的概率之和’后剩余的可能性”，这一点一定要捋明白。
这样在循环结束时，d_pe就代表了“(每一种情况发生的概率*该情况暴击所需要的次数)之和”，也即“当前C值下，打出暴击需要的平均攻击次数”，最终用倒数返回“当前C值下的综合暴击率”。
思路总结
P(N) 当次攻击的暴击概率
N 当前攻击的次数
C 概率增量
P 理论暴击率
为了让暴击之间的间隔足够均匀，暴击PRD算法被发明出来，它根据玩家未暴击的攻击次数N来逐步提升当次攻击的暴击率P(N)，以便让总暴击次数尽可能均匀地分布在总攻击次数上。
既然P(N)会随着N的不断增大而增大，那么为了让综合暴击率和理论暴击率足够贴近，必须让C（概率增量）小于或等于P（理论暴击率）。由于(0,P]是一个具有无穷多个数且有序递增的区间，因此我们采用有序查找最快的“二分查找”算法来找出合适的C值。为了防止算法无止境的运行，我们给两个暴击率设置了一个足够小的接近程度差值，以确保算法足够快且准确地得出结果。
c_from_p函数中的每一次循环都是在(0,P]中选择一个中值去“试”。如果试出来的综合暴击率大于理论暴击率，缩小上界，否则缩小下界，直到试出来的综合暴击率足够贴近理论暴击率为止；
p_from_c函数中，根据最大暴击范围枚举出每一种情况，并将它们的发生概率和所需攻击次数累加到d_pe中作为“当前C值下，打出暴击需要的平均攻击次数”，随后用倒数返回“当前C值下的综合暴击率”，以便和理论暴击率进行比较，看看是否需要进行下一轮查找。
一些题外话
虽然暴击PRD算法有效保证了良好的暴击间隔体感度，但这个算法是有一定漏洞的。在玩家互相对抗MOBA游戏中，玩家对于攻击对象有着高可选度，而算法对此是一无所知的。这意味着玩家可以先用较低的几次概率去攻击无关紧要的小兵，然后把关键的暴击留给敌方英雄，变相提高对敌方英雄的暴击率。
要解决这个问题，可以对这个PRD算法进行改装，或是采用其它的算法，例如基于马尔科夫链的概率补偿算法等等，解决方法也不少。
不过在明日方舟这种一场战斗内攻击次数繁多、且各个角色都是自动寻找目标进行攻击的环境下，暴击PRD算法的缺点被很好的掩盖了。
完整代码
import mathdef p_from_c(c): # 根据 传入 C 值，计算该C值下，最大暴击范围的综合暴击率 d_pre_success_p = 0.0 d_pe = 0.0 # 确定最大暴击范围 n_max_fail = math.ceil(1.0 / c) for i in range(1, n_max_fail + 1): # 计算“在之前i-1次攻击均未暴击的情况下，当次攻击为首次暴击的成功概率” d_cur_p = min(1.0, i * c) * (1 - d_pre_success_p) # 将当次攻击为首次暴击的成功概率累加到一个变量中，作为“已经考虑到的成功概率范围” d_pre_success_p += d_cur_p # 根据数学期望公式计算当前C值下，打出暴击需要的平均攻击次数 d_pe += d_cur_p * i # 使用倒数，根据“当前C值下，打出暴击需要的平均攻击次数”求出“当前C值下的综合暴击率” return 1.0 / d_pedef c_from_p(p): # 根据传入的暴击率，计算 PRD 算法中的概率增量 C # 初始化上界为输入概率p d_up = p # 初始化下界为0 d_low = 0.0 # 使用无限循环进行二分查找 while True: # 取上下界的中值作为待测的概率增量 d_mid = (d_up + d_low) / 2.0 # 将中值当做概率增量去算综合暴击率 d_p_tested = p_from_c(d_mid) # 如果当次计算出的综合暴击率与理论暴击率的差值已经足够小，那么可以认为已经找到了符合要求的C值，这个时候退出循环 if abs(d_p_tested - p) <= 0.000005: break # 若新计算的综合暴击率较大，则调整上界 if d_p_tested > p: d_up = d_mid else: # 否则调整下界 d_low = d_mid # 循环结束后返回最终估算的综合暴击率 return d_midprint(c_from_p(0.7)) # 计算在理论暴击率为0.7的情况下，概率增量C的值
好文章，顶！